#include "State.h"
#include "Logger.h"
using namespace std;

//constructor
State::State()
{
    gameover = 0;
    turn = 0;
};

//deconstructor
State::~State()
{
};

//sets the state up
void State::setup()
{
    grid = vector<vector<Square> >(rows, vector<Square>(cols, Square()));
};

//resets all non-wall squares to land and clears the bots ant vector
void State::reset()
{
    ants.clear();
    enemies.clear();
    food.clear();
    foodTrackingPathLengths.clear();
    for(int row=0; row<rows; row++)
        for(int col=0; col<cols; col++)
            if(!grid[row][col].isWater)
                grid[row][col].reset();
};

//outputs move information to the engine
void State::makeMove(const Location &loc, int direction)
{
    cout << "o " << loc.row << " " << loc.col << " " << CDIRECTIONS[direction] << endl;
    Logger::theLogger() << "Issuing order : " << loc.row << "," << loc.col << "," << CDIRECTIONS[direction] << endl;
    Location nLoc = getLocation(loc, direction);
    grid[nLoc.row][nLoc.col].ant = grid[loc.row][loc.col].ant;
    grid[loc.row][loc.col].ant = -1;
};

void State::mockMakeMove(const Location& loc,int direction) {
    Location nLoc = getLocation(loc, direction);
    grid[nLoc.row][nLoc.col].ant = grid[loc.row][loc.col].ant;
    grid[loc.row][loc.col].ant = -1;
}

void State::unmakeMockMove(const Location &loc,int direction) {
    Location nLoc = getLocation(loc, direction);
    grid[loc.row][loc.col].ant = grid[nLoc.row][nLoc.col].ant;
    grid[nLoc.row][nLoc.col].ant = -1;
}

//returns the euclidean distance between two locations with the edges wrapped
double State::distance(const Location &loc1, const Location &loc2) const
{
    int d1 = abs(loc1.row-loc2.row),
        d2 = abs(loc1.col-loc2.col),
        dr = min(d1, rows-d1),
        dc = min(d2, cols-d2);
    return sqrt(dr*dr + dc*dc);
};

//returns the euclidean distance between two locations with the edges wrapped
double State::manhattan_distance(const Location &loc1, const Location &loc2) const
{
   int d1 = abs(loc1.row-loc2.row),
       d2 = abs(loc1.col-loc2.col),
       dr = min(d1, rows-d1),
       dc = min(d2, cols-d2);
   return dr+dc;
}

//returns the new location from moving in a given direction with the edges wrapped
Location State::getLocation(const Location &loc, int direction) const
{
    return Location( (loc.row + DIRECTIONS[direction][0] + rows) % rows,
                     (loc.col + DIRECTIONS[direction][1] + cols) % cols );
};

/*
    This function will update update the lastSeen value for any squares currently
    visible by one of your live ants.

    BE VERY CAREFUL IF YOU ARE GOING TO TRY AND MAKE THIS FUNCTION MORE EFFICIENT,
    THE OBVIOUS WAY OF TRYING TO IMPROVE IT BREAKS USING THE EUCLIDEAN METRIC, FOR
    A CORRECT MORE EFFICIENT IMPLEMENTATION, TAKE A LOOK AT THE GET_VISION FUNCTION
    IN ANTS.PY ON THE CONTESTS GITHUB PAGE.
*/
void State::updateVisionInformation()
{
    std::queue<Location> locQueue;
    Location sLoc, cLoc, nLoc;

    for(int a=0; a<(int) ants.size(); a++)
    {
        sLoc = ants[a];
        locQueue.push(sLoc);

        std::vector<std::vector<bool> > visited(rows, std::vector<bool>(cols, 0));

        while(!locQueue.empty())
        {
            cLoc = locQueue.front();
            locQueue.pop();

            for(int d=0; d<TDIRECTIONS; d++)
            {
                nLoc = getLocation(cLoc, d);

                if(!visited[nLoc.row][nLoc.col] && distance(sLoc, nLoc) <= viewradius)
                {
                    grid[nLoc.row][nLoc.col].lastSeen = turn;
                    locQueue.push(nLoc);
                }
                visited[nLoc.row][nLoc.col] = 1;
            }
        }
    }
};

//AnalyzeMap will update some pathfinding information that will be useful
//when finding optimal paths from locA to locB.
//This function will be called every turn to update our knowledge of map and
//improve pathfinding.
void State::analyzeMap() {
}

void State::findAntsInRadius(Location loc,double radius,vector<Location>& antList) const {

    //find friendly ant locations
    for(int i =0;i<ants.size();i++) {
	if (distance(loc,ants[i]) <= radius) {
	    antList.push_back(ants[i]);
	}
    }

    //find enemy ant locations
    for(int i =0;i<enemies.size();i++) {
	if (distance(loc,enemies[i]) <= radius) {
	    antList.push_back(enemies[i]);
	}
    }
}

//multidimensional array of visited nodes
void State::extractPath(const Location& startLoc,const vector< vector<int> >& visited,stack<int>& path) const{
    Location curLoc  = startLoc;
    //iterate till we hit the end point
    while (visited[curLoc.row][curLoc.col]!=1){
	for(int d=0;d<TDIRECTIONS;d++) {
	    Location nLoc = getLocation(curLoc,d);
	    if (visited[nLoc.row][nLoc.col]!=0 &&
		visited[nLoc.row][nLoc.col] < visited[curLoc.row][curLoc.col]) {
		//we need to index with a trick to reverse directions
		path.push((d+2)%4);
		curLoc = nLoc;
		break;
	    }
	}
    }
}

//finds the shortest path from startLoc to endLoc
bool State::findPath(const Location& startLoc,const Location& endLoc, stack<int>& path,int& numNodesExplored) const {
    queue<Location> openQueue;
    openQueue.push(startLoc);
    
    vector< vector<int> > visited(rows,vector<int>(cols,0));
    //all nodes
    int depth = 1;
    numNodesExplored = 0;
    bool found=false;
    visited[startLoc.row][startLoc.col] = depth;
    while (!openQueue.empty()) {
	numNodesExplored++;
	Location curLoc = openQueue.front();
	openQueue.pop();
	if (curLoc.row == endLoc.row && curLoc.col == endLoc.col) {
	    found = true;
	    break;
	}
	else {
	    //Search didn't terminate so explore adjoining nodes
	    depth+=1;//increase depth of search tree by 1
	    for (int d=0;d<TDIRECTIONS;d++) {
		Location nLoc = getLocation(curLoc,d);
		if ((visited[nLoc.row][nLoc.col]==0) &&// explore only unvisited nodes 
		    !grid[nLoc.row][nLoc.col].isWater && //don't route over water
		    (grid[nLoc.row][nLoc.col].lastSeen!=0) 
		    ) {
		    //if the node has not yet been visited
		    //and is not water and has been seen before
		    //then explore this node
		    visited[nLoc.row][nLoc.col] = depth;
		    openQueue.push(nLoc);
		}
	    }
	}
    }
    //if we found an ant extract the Path
    //and return the ant location and the path from the ant to the location
    if (found) {
	extractPath(endLoc,visited,path);
	return true;
    }
    else 
	return false;
}

//Returns True if a food was found
//False otherwise
//if found the second parameter is the location of the food and
//path parameter contains the full path from loc to foodLoc
bool State::findClosestFood(const Location& loc,Location& foodLoc,stack<int>& path,int& numNodesExplored) const{
  //Crappy implementation, do a BFS starting at loc till we hit a friendly ant
  //at that point terminate the ant and send it along the reverse path 
    queue< Location > openQueue;
    openQueue.push(loc);

    //We use visited to track the path and extract it once we find the target
    vector < vector<int> >  visited(rows,vector<int>(cols,0));
    //we search around the location till we hit an ant or we exhaust 
    //all nodes
    int depth = 1;
    numNodesExplored = 0;
    Location finalLoc;
    bool found=false;
    visited[loc.row][loc.col] = depth;

    while (!openQueue.empty()) {
	numNodesExplored++;
	Location curLoc = openQueue.front();
	openQueue.pop();
	if (grid[curLoc.row][curLoc.col].isFood && 
	    grid[curLoc.row][curLoc.col].ant!=0 )
//	    && 
//	    grid[curLoc.row][curLoc.col].tracking<=)//allow upto 3 ants to track same food
	{
	    finalLoc = curLoc;
	    found = true;
	    break;
	}
	else {
	    //Search didn't terminate so explore adjoining nodes
	    depth+=1;//increase depth of search tree by 1
	    for (int d=0;d<TDIRECTIONS;d++) {
		Location nLoc = getLocation(curLoc,d);
		if ((visited[nLoc.row][nLoc.col]==0) &&// explore only unvisited nodes 
		    !grid[nLoc.row][nLoc.col].isWater && //don't route over water
		    (grid[nLoc.row][nLoc.col].lastSeen!=0)  &&
		    (distance(loc,nLoc)<=viewradius)
// 		    && //don't try to explore nodes never seen
// 		    (grid[nLoc.row][nLoc.col].ant!=0)//don't try to explore routes via nodes with our ants
		    ) {
		    //if the node has not yet been visited
		    //and is not water and has been seen before
		    //then explore this node
		    visited[nLoc.row][nLoc.col] = depth;
		    openQueue.push(nLoc);
		}
	    }
	}
    }
    //if we found an ant extract the Path
    //and return the ant location and the path from the ant to the location
    if (found) {
	extractPath(finalLoc,visited,path);
	foodLoc = finalLoc;
	return true;
    }
    else 
	return false;
}

//Returns True if an enemyAnt was found
//False otherwise
//if found the second parameter is the location of the enemyAnt and
//path parameter contains the full path from loc to enemyAnt
bool State::findClosestEnemyAnt(const Location& loc,Location& antLoc,stack<int>& path,int& numNodesExplored) const {
  //Crappy implementation, do a BFS starting at loc till we hit a friendly ant
  //at that point terminate the ant and send it along the reverse path 
    queue< Location > openQueue;
    openQueue.push(loc);

    //We use visited to track the path and extract it once we find the target
    vector < vector<int> >  visited(rows,vector<int>(cols,0));
    //we search around the location till we hit an ant or we exhaust 
    //all nodes
    int depth = 1;
    numNodesExplored = 0;
    Location finalLoc;
    bool found=false;
    visited[loc.row][loc.col] = depth;

    while (!openQueue.empty()) {
	numNodesExplored++;
	Location curLoc = openQueue.front();
	openQueue.pop();
	if (grid[curLoc.row][curLoc.col].ant>0) {
	    finalLoc = curLoc;
	    found = true;
	    break;
	}
	else {
	    //Search didn't terminate so explore adjoining nodes
	    depth+=1;//increase depth of search tree by 1
	    for (int d=0;d<TDIRECTIONS;d++) {
		Location nLoc = getLocation(curLoc,d);
		if ((visited[nLoc.row][nLoc.col]==0) &&
		    !grid[nLoc.row][nLoc.col].isWater &&
		    (grid[nLoc.row][nLoc.col].lastSeen!=0)
		    ) {
		    //if the node has not yet been visited
		    //and is not water and has been seen before
		    //then explore this node
		    visited[nLoc.row][nLoc.col] = depth;
		    openQueue.push(nLoc);
		}
	    }
	}
    }
    //if we found an ant extract the Path
    //and return the ant location and the path from the ant to the location
    if (found) {
	extractPath(finalLoc,visited,path);
	antLoc = finalLoc;
	return true;
    }
    else 
	return false;
}

//Returns True if an friendlyAnt was found
//False otherwise
//if found the second parameter is the location of the enemyAnt and
//path parameter contains the full path from loc to enemyAnt
bool State::findClosestFriendlyAnt(const Location& loc,Location& antLoc,stack<int>& path,int& numNodesExplored) const {
  //Crappy implementation, do a BFS starting at loc till we hit a friendly ant
  //at that point terminate the ant and send it along the reverse path 
    queue< Location > openQueue;
    openQueue.push(loc);

    //We use visited to track the path and extract it once we find the target
    vector < vector<int> >  visited(rows,vector<int>(cols,0));
    //we search around the location till we hit an ant or we exhaust 
    //all nodes
    int depth = 1;
    numNodesExplored = 0;
    Location finalLoc;
    bool found=false;
    visited[loc.row][loc.col] = depth;

    while (!openQueue.empty()) {
	numNodesExplored++;
	Location curLoc = openQueue.front();
	openQueue.pop();
	//we don't check first location for an ant as we are usually
	//trying to find friendly ants close to another one.
	if (grid[curLoc.row][curLoc.col].ant==0 and curLoc!=loc) {
	    finalLoc = curLoc;
	    found = true;
	    break;
	}
	else {
	    //Search didn't terminate so explore adjoining nodes
	    depth+=1;//increase depth of search tree by 1
	    for (int d=0;d<TDIRECTIONS;d++) {
		Location nLoc = getLocation(curLoc,d);
		if ((visited[nLoc.row][nLoc.col]==0) &&
		    !grid[nLoc.row][nLoc.col].isWater &&
		    (grid[nLoc.row][nLoc.col].lastSeen!=0) &&
		    (distance(loc,nLoc)<=viewradius)
		    ) {
		    //if the node has not yet been visited
		    //and is not water and has been seen before
		    //then explore this node
		    visited[nLoc.row][nLoc.col] = depth;
		    openQueue.push(nLoc);
		}
	    }
	}
    }
    //if we found an ant extract the Path
    //and return the ant location and the path from the ant to the location
    if (found) {
	extractPath(finalLoc,visited,path);
	antLoc = finalLoc;
	return true;
    }
    else 
	return false;
}


/*
    This is the output function for a state. It will add a char map
    representation of the state to the output stream passed to it.

    For example, you might call "cout << state << endl;"
*/
ostream& operator<<(ostream &os, const State &state)
{
    //print some stats first
    os << "ants:" << state.ants.size() << endl;
    os << "enemies:" << state.enemies.size() << endl;
    os << "food:"  << state.food.size() << endl;
    for(int row=0; row<state.rows; row++)
    {
        for(int col=0; col<state.cols; col++)
        {
            if(state.grid[row][col].isWater)
                os << '%';
            else if(state.grid[row][col].isFood)
                os << '*';
            else if(state.grid[row][col].ant >= 0)
                os << (char)('a' + state.grid[row][col].ant);
            else if(state.grid[row][col].lastSeen == 0)
                os << '?';
            else if(state.grid[row][col].lastSeen < state.turn)
                os << '~';
            else
                os << '.';
        }
        os << endl;
    }

    return os;
};

//input function
istream& operator>>(istream &is, State &state)
{
    int row, col, player;
    string inputType, junk;

    //finds out which turn it is
    while(is >> inputType)
    {
        if(inputType == "end")
        {
            state.gameover = 1;
            break;
        }
        else if(inputType == "turn")
        {
            is >> state.turn;
            break;
        }
        else //unknown line
            getline(is, junk);
    }

    if(state.turn == 0)
    {
        //reads game parameters
        while(is >> inputType)
        {
            if(inputType == "loadtime")
                is >> state.loadtime;
            else if(inputType == "turntime")
                is >> state.turntime;
            else if(inputType == "rows")
                is >> state.rows;
            else if(inputType == "cols")
                is >> state.cols;
            else if(inputType == "turns")
                is >> state.turns;
            else if(inputType == "viewradius2")
            {
                is >> state.viewradius;
                state.viewradius = sqrt(state.viewradius);
            }
            else if(inputType == "attackradius2")
            {
                is >> state.attackradius;
                state.attackradius = sqrt(state.attackradius);
            }
            else if(inputType == "spawnradius2")
            {
                is >> state.spawnradius;
                state.spawnradius = sqrt(state.spawnradius);
            }
            else if(inputType == "ready") //end of parameter input
            {
                state.timer.start();
                break;
            }
            else    //unknown line
                getline(is, junk);
        }
    }
    else
    {
        //reads information about the current turn
        while(is >> inputType)
        {
            if(inputType == "w") //water square
            {
                is >> row >> col;
                state.grid[row][col].isWater = 1;
            }
            else if(inputType == "f") //food square
            {
                is >> row >> col;
                state.grid[row][col].isFood = 1;
                state.food.push_back(Location(row, col));
            }
            else if(inputType == "a") //live ant square
            {
                is >> row >> col >> player;
                state.grid[row][col].ant = player;
                if(player == 0)
                    state.ants.push_back(Location(row, col));
                else
                    state.enemies.push_back(Location(row, col));
            }
            else if(inputType == "d") //dead ant square
            {
                is >> row >> col >> player;
                state.grid[row][col].deadAnts.push_back(player);
            }
            else if(inputType == "players") //player information
                is >> state.noPlayers;
            else if(inputType == "scores") //score information
            {
                state.scores = vector<double>(state.noPlayers, 0.0);
                for(int p=0; p<state.noPlayers; p++)
                    is >> state.scores[p];
            }
            else if(inputType == "go") //end of turn input
            {
                if(state.gameover)
                    is.setstate(std::ios::failbit);
                else
                    state.timer.start();
                break;
            }
            else //unknown line
                getline(is, junk);
        }
    }

    return is;
};
